package com.xw.class13;

/**
 * @author XW
 * @data 2024/7/20 20:31
 * @description 返回最大二叉搜索子树头结点
 */
public class Code02_MaxSubBSTHead {

    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int value) {
            val = value;
        }
    }

    public static class Info{
        public int min;
        public int max;
        public int allSize;
        public int maxBSTSubTreeSize;

        public TreeNode node;

        public Info(int min, int max, int allSize, int maxBSTSubTreeSize, TreeNode node) {
            this.min = min;
            this.max = max;
            this.allSize = allSize;
            this.maxBSTSubTreeSize = maxBSTSubTreeSize;
            this.node = node;
        }
    }

    public static TreeNode maxSubBSTHead(TreeNode head){
        if(null == head){
            return null;
        }

        return process(head).node;
    }

    private static Info process(TreeNode head) {
        if(null == head){
            return null;
        }
        Info leftInfo = process(head.left);
        Info rightInfo = process(head.right);
        int min = head.val;
        int max = head.val;
        int allSize = 1 ;
        int p1 = -1;
        int p2 = -1;
        TreeNode node = null ;

        if(null != leftInfo){
            min = Math.min(min, leftInfo.min);
            max = Math.max(max, leftInfo.max);
            allSize += leftInfo.allSize;
            p1 = leftInfo.maxBSTSubTreeSize;
        }
        if(null != rightInfo){
            min = Math.min(min, rightInfo.min);
            max = Math.max(max, rightInfo.max);
            allSize += rightInfo.allSize;
            p2 = rightInfo.maxBSTSubTreeSize;
        }
        boolean leftIsBST = null == leftInfo ? true : leftInfo.maxBSTSubTreeSize == leftInfo.allSize;
        boolean rightIsBST = null == rightInfo ? true : rightInfo.maxBSTSubTreeSize == rightInfo.allSize;
        int p3 = -1;
        if(leftIsBST){
            node = head.left;
        }
        if(rightIsBST){
            node = head.right;
        }
        if(leftIsBST && rightIsBST){
            boolean leftMaxLessHead = null == leftInfo ? true : leftInfo.max < head.val;
            boolean rightMinMoreHead = null == rightInfo ? true : rightInfo.min > head.val;
            if(leftMaxLessHead && rightMinMoreHead){
                int leftSize = leftInfo == null ? 0 : leftInfo.allSize;
                int rightSize = rightInfo == null ? 0 : rightInfo.allSize;
                p3 = leftSize + rightSize + 1;
                node = head;
            }
        }


        return new Info(min, max, allSize, Math.max(Math.max(p1, p2), p3), node);
    }
}
